using System;
using System.Text;
using System.Linq;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0214. 最短回文串")]
    public class No0214_ShortestPalindrome : AbsBaseTestItem
    {
        /*
        给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
        */

        public override void OnTest()
        {
            Assert.TestExe(ShortestPalindrome, "aacecaaa", "aaacecaaa");
            Assert.TestExe(ShortestPalindrome, "abcd", "dcbabcd");

            Assert.TestExe(ShortestPalindrome_2, "aacecaaa", "aaacecaaa");
            Assert.TestExe(ShortestPalindrome_2, "abcd", "dcbabcd");
        }

        /// <summary>
        /// 方法一：字符串哈希
        /// </summary>
        public string ShortestPalindrome(string s)
        {
            int n = s.Length;
            int basevalue = 131, mod = 1000000007;
            int left = 0, right = 0, mul = 1;
            int best = -1;
            for (int i = 0; i < n; ++i)
            {
                left = (int)(((long)left * basevalue + s[i]) % mod);
                right = (int)((right + (long)mul * s[i]) % mod);
                if (left == right)
                {
                    best = i;
                }
                mul = (int)((long)mul * basevalue % mod);
            }
            string add = (best == n - 1 ? "" : s.Substring(best + 1));
            StringBuilder ans = new StringBuilder();
            ans.Append(add.Reverse().ToArray());
            ans.Append(s);
            return ans.ToString();
        }

        /// <summary>
        /// 方法二：KMP 算法
        /// </summary>
        public string ShortestPalindrome_2(string s)
        {
            int n = s.Length;
            int[] fail = new int[n];
            Array.Fill(fail, -1);
            for (int i = 1; i < n; ++i)
            {
                int j = fail[i - 1];
                while (j != -1 && s[j + 1] != s[i])
                {
                    j = fail[j];
                }
                if (s[j + 1] == s[i])
                {
                    fail[i] = j + 1;
                }
            }
            int best = -1;
            for (int i = n - 1; i >= 0; --i)
            {
                while (best != -1 && s[best + 1] != s[i])
                {
                    best = fail[best];
                }
                if (s[best + 1] == s[i])
                {
                    ++best;
                }
            }
            string add = (best == n - 1 ? "" : s.Substring(best + 1));
            StringBuilder ans = new StringBuilder();
            ans.Append(add.Reverse().ToArray());
            ans.Append(s);
            return ans.ToString();
        }
    }
}
